// https://www.lintcode.com/problem/search-a-2d-matrix-ii/description

class Solution {
public:

// 注意和search-a-2d-matrix对比，不可以用普通二分法做(或者每一行来做二分也可以..)
//     bool searchMatrix(vector<vector<int>>& matrix, int target) {
//         if (matrix.empty() || matrix[0].empty()) return false;
// // Input
// // [[]]
// // 1
// // Expected
// // 0
        
//         int m = matrix.size();
//         int n = matrix[0].size();
//         int begin = 0;
//         int end = m - 1;
//         int line = -1;
//         while (begin + 1 < end)
//         {
//             int mid = (end - begin) / 2 + begin;
//             if (matrix[mid][0] == target)
//                 return true;
//             else if (matrix[mid][0] < target)
//             {
//                 begin = mid;
//             }
//             else
//             {
//                 end = mid;
//             }
//         }
//         if (matrix[end][0] < target)
//             line = end;
//         else line = begin;
//         cout << line << endl;
//         begin = 0;
//         end = n - 1;
//         while (begin + 1 < end)
//         {
//             int mid = (end - begin) / 2 + begin;
//             if (matrix[line][mid] == target)
//                 return true;
//             else if (matrix[line][mid] < target)
//                 begin = mid;
//             else 
//                 end = mid;
//         }
//         if (matrix[line][begin] == target || matrix[line][end] == target)
//             return true;
//         return false;
//     }


    
    // BFS TLE
    // struct Node
    // {
    //     int x;
    //     int y;
    // };
    // int searchMatrix(vector<vector<int>>& matrix, int target) {
    //     if (matrix.empty() || matrix[0].empty()) return false;
    //     queue<Node> q;
    //     int cnt = 0;
    //     int right[2] = {0, 1};
    //     int down[2] = {1, 0};
    //     q.push(Node{0, 0});
    //     while (!q.empty())
    //     {
    //         Node tmp = q.front();
    //         q.pop();
    //         cout << tmp.x << endl;
    //         cout << tmp.y << endl;
    //         if (matrix[tmp.x][tmp.y] == target)
    //         {
    //             cnt++;
    //             cout << cnt << endl;
    //         }
    //         int nx;
    //         int ny;
    //         if (tmp.x == 0) // 防止重复
    //         {
    //             nx = tmp.x + right[0];
    //             ny = tmp.y + right[1];
    //             if (nx < matrix.size() && ny < matrix[0].size())
    //             {
    //                 q.push(Node{nx, ny});
    //             }
    //         }
    //         nx = tmp.x + down[0];
    //         ny = tmp.y + down[1];
    //         if (nx < matrix.size() && ny < matrix[0].size())
    //         {
    //             q.push(Node{nx, ny});
    //         }
    //     }
    //     return cnt;
    // }


    // 法一：
    // 从左下角开始，往右上角逼近
    // int searchMatrix(vector<vector<int>>& matrix, int target) {
    //     if (matrix.empty() || matrix[0].empty())
    //     {
    //         return 0;
    //     }
    //     int m = matrix.size();
    //     int n = matrix[0].size();
    //     int i = m - 1;
    //     int j = 0;
    //     int occur = 0;
    //     while (i >= 0 && j < n)
    //     {
    //         if (matrix[i][j] == target)
    //         {
    //             occur++;
    //             cout << i << j << endl;
    //             cout << occur << endl;
    //         }
    //         if (matrix[i][j] < target)
    //         {
    //             ++j;
    //         }
    //         else
    //         {
    //             --i;
    //         }
    //     }
    //     return occur;
    // }
    
    
    // 法二：
    // 区间二分
    int searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) 
            return false;
        int n = matrix.size();
        int m = matrix[0].size();
        int l = matrix[0][0];
        int r = matrix[n - 1][m - 1];
        int cnt = 0;
        while (l < r) //l + 1 < r那种写法最后cnt不知道怎么判断，改成这种，更新时候l = mid + 1
        {
            int mid = (r - l) / 2 + l;
            int i = n - 1;
            int j = 0;
            cnt = 0; //每次cnt重新算，在一次二分里面才不会重复

            while (i >= 0 && j < m) 
            {
                if (matrix[i][j] == target)
                    cnt++; 
                if (matrix[i][j] <= mid) 
                {
                    j++;
                }
                else
                {
                    i--;
                }
                // if (matrix[i][j] == target)
                //     cnt++;
            }
            // 注意，出来了就没i j什么事了
            if (mid < target)
                l = mid + 1;
            else
                r = mid;
            
        }
        // if (l == target)
        //     cnt++;
        // if (r == target)
        //     cnt++;
        return cnt;
    }
};